import java.util.Scanner;

/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/6/5
 * Time:21:34
 **/
public class Main1 {
    /**
     * 每日一题-斐波那契凤尾
     * @param args
     */
    public static void main(String[] args) {
        int border = -1;
        long[] ans = new long[100000];
        ans[0] = 1;
        ans[1] = 2;
        for(int i = 2; i< 100000; i++) {
            long next = ans[i-1] + ans[i-2];
            if(border == -1 && next >= 100000){
                border = i+1;
            }
            ans[i] = next % 1000000;
        }
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            long f = ans[n-1];

            if(n<border){
                System.out.printf("%d\n",f);
            }else{
                System.out.printf("%06d\n",f);
            }
        }
    }
}
